//
// Description: 快速排序 模板
// Created by Loading on 2021/8/23.
//

#include <bits/stdc++.h>

using namespace std;

/* 快速排序，递归法 */
void quick_sort(vector<int> &nums, int l, int r) {
    if (l >= r) {
        return;
    }
    // 用第一个元素作为枢轴
    int key = nums[l];
    int i = l, j = r;
    cout << "key:" << key << ", ";

    while (i < j) {
        // 从后往前，寻找小于枢轴的值
        while (i < j && nums[j] >= key) {
            --j;
        }
        // 找到后 赋值到前面
        nums[i] = nums[j];
        // 从前往后，寻找大于枢轴的值
        while (i < j && nums[i] <= key) {
            ++i;
        }
        // 找到后 赋值到后面
        nums[j] = nums[i];
    }
    // 循环结束后，i 和 j 均指向枢轴位置，将枢轴放置
    nums[i] = key;
    for (auto &x : nums) {
        cout << x << " ";
    }
    cout << endl;

    // 分治法，左右两个区间分别排序，递归
    quick_sort(nums, l, i - 1);
    quick_sort(nums, i + 1, r);
}

/* 快速排序，迭代法 */
void quick_sort2(vector<int> &nums) {
    // 使用 stack 维护区间
    stack<pair<int, int>> s;
    s.emplace(pair<int, int>{0, nums.size() - 1});
    while (!s.empty()) {
        auto p = s.top();
        s.pop();
        int l = p.first, r = p.second;
        int key = nums[l];
        cout << "key:" << key << ", ";

        while (l < r) {
            while (l < r && nums[r] >= key) {
                --r;
            }
            nums[l] = nums[r];
            while (l < r && nums[l] <= key) {
                ++l;
            }
            nums[r] = nums[l];
        }
        nums[l] = key;
        for (auto &x : nums) {
            cout << x << " ";
        }
        cout << endl;
        // 如果区间不存在，无需压栈
        if (p.first < l - 1) {
            s.emplace(pair<int, int>{p.first, l - 1});
        }
        if (l + 1 < p.second) {
            s.emplace(pair<int, int>{l + 1, p.second});
        }
    }
}

int main() {
    vector<int> nums = {4, 1, 7, 6, 9, 2, 8, 0, 3, 5};
    // 递归
//    quick_sort(nums, 0, (int) nums.size() - 1);
    // 迭代
    quick_sort2(nums);
    for (auto &x : nums) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}